from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def carPooling(self, trips, inc):
        n = 1001 # 题目说最长不超过1000个
        arr = [0] * n
        df = self.Deffrent(arr)
        for i in trips:
            inc1 = i[0]
            left = i[1]
            right = i[2]-1
            df.increment(left,right,inc1)
        res = df.result()
        if max(res) > inc:
            return False
        else:
            return True
    class Deffrent():
        def __init__(self,arr):
            n = len(arr)
            self.dp = [arr[0]] + [arr[i]-arr[i-1] for i in range(1,n)]
        def increment(self,left,right,inc):
            self.dp[left] += inc
            if right+1 < len(self.dp):
                self.dp[right+1] -= inc
        def result(self):
            res = [0]*len(self.dp)
            res[0] = self.dp[0]
            for i in range(1,len(self.dp)):
                res[i] = self.dp[i]+res[i-1]
            return res

        
# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = Solution()
    print(solution.carPooling([[9,0,1],[3,3,7]],4))
    # your test code here